/**
 * @file   IntervalTree.h
 * @author zhang-zh
 * @date   2020.12.20 Sunday
 * 
 * @brief  A headfile for Interval Tree.
 * 
 */

#ifndef __zhang_intervaltree__
#define __zhang_intervaltree__

#include "RedBlackTree.h"

class IntervalTree : public RedBlackTree<double>
{
public:
    typedef RedBlackTree<double>::Node Node;
    
    /**
     * Constructor.
     * 
     */
    IntervalTree() : RedBlackTree<double>()
    {
        nil->high = 0;
        nil->maximum = 0;
    };

    /**
     * Destructor.
     * 
     */
    ~IntervalTree(){};

    /**
     * Insert a new node to the tree, and keep it as a interval tree.
     * @param _low The low limit of the interval.
     * @param _high The high limit of the interval.
     * 
     * @return 0 for OK.
     */
    virtual int insert(double _low, double _high);

    virtual int insert(Node* _new)
    {
        _new->maximum = _new->high;
        _new->color = RED;
        RedBlackTree<double>::insert(_new);

    };

    /**
     * Delete the node and keep it still as a interval tree.
     * @param _x The node to be deleted.
     * 
     * @return 0 for OK.
     */
    virtual int del(Node *_x);

    /**
     * Search for the refered node. 
     * @param _low The low limit of the node.
     * @param _high The high limit of the node.
     * 
     * @return The node or NULL.
     */
    Node* lookup(double _low, double _high);

};

int IntervalTree::insert(double _low, double _high)
{
    Node* _new = new Node;
    _new->data = _low;
    _new->high = _high;
    _new->maximum = _high;
    _new->color = RED;
///    _new->parent = _new->left = _new->right = this->nil;
    RedBlackTree<double>::insert(_new);

    return 0;
}

int IntervalTree::del(Node* _x)
{
    RedBlackTree<double>::del(_x);
}

IntervalTree::Node* IntervalTree::lookup(double _low, double _high)
{
    Node* x = root;
    while(x != nil && (_low > x->high || _high < x->low))
    {
        if (x->left != nil && _low <= x->left->maximum)   
            x = x->left;
  	    else
            x = x->right;
    }
    
    return x;
}
                                         

#endif
